The present invention relates to syndrome calculating apparatus, and more particularly to syndrome calculating apparatus for obtaining syndromes from received codes where random errors and the like in received data are to be corrected with the Reed Solomon Code which is a kind of the BCH Code (Bose-Chaudhuri-Hocquenghem Code) used as an error correcting code.
In digital data transmission of high reliability, data are transmitted as coded in order to detect error patterns in received data and correct errors. In such case, it is most preferable to use, as an error correcting code, the Reed Solomon Code which has the highest correcting ability for random errors and which is a kind of the BCH Code.
In particular, optical disks recently developed present a higher error rate due to surface roughness of the optical disks themselves, turbulency of servo or the like, as compared with a magnetic disk device commonly used in the prior art. It is therefore indispensable to incorporate in an optical disk reproducing device a decoding device for detecting and correcting errors in data read from the optical disks.
Such decoding includes the following steps of:
(1) obtaining syndromes from a received data; PA0 (2) obtaining the number of error locations from the syndromes; PA0 (3) obtaining the dimension of an error; and PA0 (4) executing error correction.
The Reed Solomon Code is constituted by the elements in the Galois field GF (q.sup.m). For a digital circuit, q=2 can be established. When the primitive element of this Galois field GF (2.sup.m) is .alpha., the following equation is established: EQU .alpha..sup.2.spsp.m.sup.-1 =1
When m bits constitute 1 symbol, the generator polynomial for error correction of t symbols can be expressed by the following equation: EQU g (x)=(x-.alpha.)(x-.alpha..sup.2) . . . (x-.alpha..sup.2t), or EQU g (x)=(x-1)(x-.alpha.) . . . (x-.alpha..sup.2t-1)
The code polynomial of a transmission code of a data symbol added by an inspection symbol is expressed by the following equation: ##EQU1##
Accordingly, when f (x) is equal to 0, then 1, .alpha., .alpha..sup.2, . . . , .alpha..sup.2t-1, or .alpha., .alpha..sup.2, . . . , .alpha..sup.2t are the root.
That is, the following equations are established: ##EQU2##
In fact, when the transmission code above-mentioned (b.sub.0, b.sub.1, . . . , b.sub.n-1) is transmitted and received, it is not ensured at all that the received code (a.sub.0, a.sub.1, . . . , a.sub.n-1) is the same as the transmission code and it is therefore not ensured that 0 is obtained for all equations above-mentioned.
Therefore, the following equations are established: ##EQU3##
S.sub.i (i=0, 1, . . . 2t) becomes 0 when the transmission code has been received without errors, but it becomes other value than 0 if the transmission code has been erroneously received. Such S.sub.i is defined as a syndrome.
Therefore, from syndromes S.sub.0, S.sub.1, . . . , S.sub.2t-1 obtained according to the equations above-mentioned, an error location polynomial is obtained. Then, the inverse elements of the roots of the error location polynomial can be obtained so that the error locations are obtained and the error are corrected.
In a series of the calculations above-mentioned, the calculations for obtaining the respective syndromes S.sub.0, S.sub.1, . . . , S.sub.2t-1 are surprisingly troublesome. In order to carry out these calculations at a high speed, there has been conventionally proposed syndrome calculating apparatus constituted by, for example, ROM tables and shift registers (Unexamined Patent Publication No. 5759/1984).
This syndrome calculating apparatus above-mentioned is designed to calculate the following equations faithfully: ##EQU4##
It is therefore required to use ROMs having an excessively great capacity, and the syndrome calculating time cannot be sufficiently shortened, as a whole.